/**
 * @file     climbStairs.js
 * @brief    [70. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)
 * @author   Zhu
 * @date     2022-04-02 13:31
 */

/**
 * 递归
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    return climbStairs(n - 1) + climbStairs(n - 2);
};

/**
 * dp - 数组
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    const dp = [0, 1, 2];
    let i = 3;
    while (i <= n) {
        dp[i] = dp[i - 1] + dp[i - 2];
        i++;
    }
    return dp[n];
};

/**
 * dp-滚动数组，优化空间
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    let pre2 = 0,
        pre1 = 0,
        cur = 1;
    while (n--) {
        pre2 = pre1;
        pre1 = cur;
        cur = pre1 + pre2;
    }
    return cur;
};
